package lc;

public class Ex37 {
    class Solution {

        //有丶像布隆过滤器
        //利用三个boolean数组，对一个位置进行三次判别，快速定位一个位置能否插入元素
        
        /**
        创新点：
        1. 对于一个方形区域也可以通过一个9*9的坐标来表示数字使用，即第一位表示这个方形区域是第几个，第二位表示使用了哪个数字
        2. 字符转数字使用board[i][j] - '1', 可以将下标映射到0~8
        */
    
        boolean[][] row = new boolean[9][9], col = new boolean[9][9], sq = new boolean[9][9];
        char board[][];
        public void solveSudoku(char[][] board) {
            this.board = board;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') {
                        int n = board[i][j] - '1';
                        row[i][n] = true;//第(i + 1)行的数字(n + 1)被使用了
                        col[j][n] = true;//第(j + 1)列的数字(n + 1)。。。
    
                        //牛逼的地方
                        int k = (i / 3) * 3 + j / 3; //第k个矩阵的数字(n + 1)...
                        sq[k][n] = true;
                    }
                }
            }
            dfs(0);
        }
    
        private boolean dfs(int cur) {
            if (cur == 81) {
                //填充完毕且正确
                return true;
            }
            //计算当前的行列值
            int r = cur / 9, c = cur % 9, k = (r / 3) * 3 + c / 3;
            if (board[r][c] == '.') 
                return dfs(cur + 1);
            for (int n = 0; n < 9; n++) {
                if (row[r][n] || col[c][n] || sq[k][n]) continue;
    
                //填充这个位置，看后面的情况
                row[r][n] = col[c][n] = sq[k][n] = true;
                if (dfs(cur + 1)) {
                    return true;
                }
                row[r][n] = col[c][n] = sq[k][n] = false; //分支回溯
            }
            return false;
        }
    }
}
